#include "../../tools.h"

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int M = obstacleGrid.size(), N = obstacleGrid[0].size();
        if(obstacleGrid[M - 1][N - 1] == 1) return 0;

        vector<vector<long>> dp(M + 1, vector<long>(N + 1, 0));
        dp[M - 1][N - 1] = 1;

        for(int i = M - 1; i > -1; --i){
            for(int j = N - 1; j > -1; --j){
                if(i == M - 1 && j == N - 1) continue;
                if(obstacleGrid[i][j] == 1) continue;

                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
        return dp[0][0];
    }
};



int main(int argc, char const *argv[])
{
    vector<vector<int>> vv = {{0,0},{1,0}};//{{0,0,0},{0,1,0},{0,0,0}};

    Solution s;
    cout << s.uniquePathsWithObstacles(vv);

    return 0;
}
